/*
* FILENAME:		stack_app.c/stack_app.h 
* CREATED AT:		2012/Jun/4
* DECRITION:		the module stack, some application area of stack
* 
* MODULE:		linead list
* PLATFORM:		ubuntu-12.04/gcc-4.6.3
* AUTHOR:		incarnation-lee
* 
* ----------------------REVISION HISTROY------------------------
* No.	Date	Revised by	Function	Descrition
* 1	12/6/4	incar-lee	stack_convert,	Hex convert
				stack_app_demo
  2	12/6/5	incar-lee	stack_match	matching parenthese
  3	12/6/10	incar-lee	stack_ledit	line editor
  4	12/6/10	incar-lee	stack_detect	detect path
				loc_next				
  5	12/6/11	incar-lee	stack_detect	find all path, improve the loc_next color algorithm
  6	12/6/14	incar-lee	stack_exp	compute expression in two stack, one for number, other for operator
*
*/

/* Standard C */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <errno.h>

/* linux related */
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>

/* user defined */
#include "externals.h"
#include "udgtd.h"
#include "stack_app.h"
#include "errcode.h"


/* 
* maze for detect ,0 means path and 1 equal wall 
* maze_dt[y][x]
*/
static const signed short maze_dt[10][10] = {
	{1,1,1,1,1,1,1,1,1,1,},
	{1,0,0,1,0,0,0,1,0,1,},
	{1,0,0,1,0,0,0,1,0,1,},
	{1,0,0,0,0,1,1,0,0,1,},
	{1,0,1,1,1,0,0,0,0,1,},
	{1,0,0,0,1,0,0,0,0,1,},
	{1,0,1,0,0,0,1,0,0,1,},
	{1,0,1,1,1,0,1,1,0,1,},
	{1,1,0,0,0,0,0,0,0,1,},
	{1,1,1,1,1,1,1,1,1,1,},
};

static S_mazepath start	= {
	.x=1,
	.y=1,
};

static S_mazepath end = {
	.x=8,
	.y=8,
};

/* 
* the main control function of demo stack applications
*/
STATUS stack_app_demo()
{
	STATUS result = 0;

	/* Hex convert in stack */
	result = stack_convert();
	if(__builtin_expect(!!result,0))
		return -1;

	/* Matching the parenthesis */
	result = stack_match();
	if(__builtin_expect(!!result,0))
		return -1;

	/* line editor */
	result = stack_ledit();
	if(__builtin_expect(!!result,0))
		return -1;

	/* maze detect */
	result = stack_detect();
	if(__builtin_expect(!!result,0))
		return -1;

	/* get value of expression */
	result = stack_expression();
	if(__builtin_expect(!!result,0))
		return -1;
	return 0;
}


/* 
* the Hex convert from DEC to OCT 
*/
STATUS stack_convert()
{
	S_sqstack sk_convert;
	STATUS result = 0;
	unsigned int N = 2347;			/* this input N also come from stdin user either */
	S_element ele;

	fprintf(stdout,"Dec:%d\nOct:",N);
	memset(&ele,0,sizeof(S_element));
	result = init_sqk(&sk_convert);	
	if(__builtin_expect(!!result,0))
		return -1;
	
	while(0!=N)
	{
		ele.value = N % OCT;
		if(__builtin_expect(!!push_sqk(&sk_convert,&ele),0))
			return -1;
		N>>=OCTBits;	
	}
	
	while(sk_convert.base!=sk_convert.top)
	{
		if(__builtin_expect(!!pop_sqk(&sk_convert,&ele),0))
			return -1;
		fprintf(stdout,"%d",ele.value);
	}	
	fprintf(stdout,"\n");
	clear_sqk(&sk_convert);
	destory_sqk(&sk_convert);
	return 0;
}


/*
* Matching the parenthesis 
*/
STATUS stack_match()
{
	S_sqstack sk_match;
	STATUS result = 0;
	S_element ele;
	char *parenthese = "[[([])(([]))]";		/* this source data can be a arg from usr stdin */
	
	memset(&ele,0,sizeof(S_element));
	result = init_sqk(&sk_match);
	if(__builtin_expect(!!result,0))
		return -1;
	fprintf(stdout,"%s\n",parenthese);

	while('\0'!=*parenthese)
	{
		if(__builtin_expect(!!isEmpty_sqk(&sk_match),1))
		{
			if(isMatch(top_sqk(&sk_match)->name,*parenthese))
			{
				if(__builtin_expect(!!pop_sqk(&sk_match,&ele),0))
					return -1;
			}
			else
			{
				ele.name = *parenthese;
				if(__builtin_expect(!!push_sqk(&sk_match,&ele),0))
					return -1;		
			}
		}
		else							/* Empty happened only once */
		{
			ele.name = *parenthese;	
			if(__builtin_expect(!!push_sqk(&sk_match,&ele),0))
				return -1;		
		}
		parenthese++;
	}	
	
	if(0==isEmpty_sqk(&sk_match))
		fprintf(stdout,"Matched.\n");	
	else
		fprintf(stdout,"UnMatched.\n");	

	clear_sqk(&sk_match);
	destory_sqk(&sk_match);
	return 0;		
}


/*
* line editer, # means backspace and @ will delete the whole line
* otherwise \0 exit editer
*/
STATUS stack_ledit(void)
{
	STATUS result = 0;
	S_sqstack sk_le;	
	S_element ele,*btn;
	char *usr_in = "for(@whli##ilr#e(s#*s)";		/* or from user stdin */

	memset(&ele,0,sizeof(S_element));
	result = init_sqk(&sk_le);
	if(__builtin_expect(!!result,0))
		return -1;

	fprintf(stdout,"%s\n",usr_in);
	while('\0'!=*usr_in++)
	{
		if(__builtin_expect(!!isEmpty_sqk(&sk_le),1))
		{
			if('#'==*usr_in)
			{
				if(__builtin_expect(!!pop_sqk(&sk_le,(S_element*)0),0))
					return -1;
			}
			else if('@'==*usr_in)
			{
				if(__builtin_expect(!!clear_sqk(&sk_le),0))
					return -1;
			}
			else
			{
				ele.name = *usr_in;
				if(__builtin_expect(!!push_sqk(&sk_le,&ele),0))
					return -1;
			}
		}
		else					/* specify when empty stack */
		{
			if('#'==*usr_in || '@'==*usr_in)
				continue;	
			ele.name = *usr_in;
			if(__builtin_expect(!!push_sqk(&sk_le,&ele),0))
				return -1;
		}
	}
	
	/* print the input result */
	btn = sk_le.base;
	while('\0'!=btn->name)
	{
		fprintf(stdout,"%c",(btn++)->name);	
	}

	fprintf(stdout,"\n");
	clear_sqk(&sk_le);
	destory_sqk(&sk_le);
	return 0;
}


/*
* detect the maze available path
*/
STATUS stack_detect()
{
	STATUS result = 0;
	int i;
	S_sqstack sk_dt;		
	S_element ele,*prst;

	result = init_sqk(&sk_dt);
	if(__builtin_expect(!!result,0))
		return -1;
	
	memset(&ele,0,sizeof(S_element));				/* locate the start point */
	ele.sp = start;
	if(__builtin_expect(!!push_sqk(&sk_dt,&ele),0))
		return -1;

	while(isEmpty_sqk(&sk_dt))
	{
		memset(&ele,0,sizeof(S_element));				/* locate the start point */
		result = loc_next(&sk_dt,&ele);
		if(1==result)							/* can not move anymore */
		{
			if(__builtin_expect(!!pop_sqk(&sk_dt,(S_element*)0),0))
				return -1;
		}
		else
		{
			if(__builtin_expect(!!push_sqk(&sk_dt,&ele),0))
				return -1;
			if(0==memcmp(&end,&ele.sp,(size_t)&((S_mazepath*)0)->color))	/* get a path */
			{
				prst = sk_dt.base;
				for(i=0;i<length_sqk(&sk_dt);i++)
				{
					/* uncommit blow line print all the path */
					/* fprintf(stdout,"(%d,%d)->",prst->sp.x,prst->sp.y); */
					prst++;
				}					
				/* fprintf(stdout,"\n"); */
			}
		}	
	}
	clear_sqk(&sk_dt);
	destory_sqk(&sk_dt);
	return 0;
}

/*
* find the next location,
* Attion:for reduece handle edger, which can 
* add wall around the maze table, 
*
* return 0 when available, 1 no way found
*/
static STATUS loc_next(S_sqstack *sk_dt,S_element *ele)
{
	S_element *top = top_sqk(sk_dt);
	do
	{
		if(0==maze_dt[top->sp.y-1][top->sp.x] &&
			0==(top->sp.color & 1<<UP))
		{
			if(isContain_sqk(sk_dt,ele))				/* if not contains */	
			{
				ele->sp.x = top->sp.x;
				ele->sp.y = top->sp.y - 1;
				top->sp.color =	COLOR_BIT(top->sp.color,UP);	/* set top location, colored */	
				ele->sp.color = COLOR_BIT(ele->sp.color,DOWN);	/* set the push location */
				return 0;
			}
		}
		else
			top->sp.color =	COLOR_BIT(top->sp.color,UP);
			
		if(0==maze_dt[top->sp.y][top->sp.x+1] &&
			0==(top->sp.color & 1<<RIGHT))
		{
			if(isContain_sqk(sk_dt,ele))	
			{	
				ele->sp.x = top->sp.x + 1;
				ele->sp.y = top->sp.y;
				top->sp.color =	COLOR_BIT(top->sp.color,RIGHT);		
				ele->sp.color = COLOR_BIT(ele->sp.color,LEFT);
				return 0;
			}
		}
		else
			top->sp.color =	COLOR_BIT(top->sp.color,RIGHT);

		if(0==maze_dt[top->sp.y+1][top->sp.x] &&
			0==(top->sp.color & 1<<DOWN))
		{
			if(isContain_sqk(sk_dt,ele))		
			{
				ele->sp.x = top->sp.x;
				ele->sp.y = top->sp.y + 1;
				top->sp.color =	COLOR_BIT(top->sp.color,DOWN);		
				ele->sp.color = COLOR_BIT(ele->sp.color,UP);
				return 0;
			}
		}
		else
			top->sp.color =	COLOR_BIT(top->sp.color,DOWN);

		if(0==maze_dt[top->sp.y][top->sp.x-1] &&
			0==(top->sp.color & 1<<RIGHT))
		{
			if(isContain_sqk(sk_dt,ele))	
			{
				ele->sp.x = top->sp.x - 1;
				ele->sp.y = top->sp.y;
				top->sp.color =	COLOR_BIT(top->sp.color,LEFT);		
				ele->sp.color = COLOR_BIT(ele->sp.color,RIGHT);
				return 0;
			}
		}
		else
			top->sp.color =	COLOR_BIT(top->sp.color,LEFT);
	}while(0);
	return 1;	
}

/* 
* get the value of expression 
*/
STATUS stack_expression()
{
	STATUS result = 0;
	S_sqstack stack_op,stack_nu;
	S_element ele,*top_op,l_nu,r_nu,top;
	char exp[] = {4,'+',2,'*','(',13,'-',1,'+',8,')','/',4,};			/* "4+2*(13-1)/4" */
	char *ep = exp;

	fprintf(stdout,"4+2*(13-1+8)/4=");
	memset(&ele,0,sizeof(S_element));
	result = init_sqk(&stack_op);
	if(__builtin_expect(!!result,0))
		return -1;
	result = init_sqk(&stack_nu);
	if(__builtin_expect(!!result,0))
		return -1;
	
	ele.name = '\0';						/* init the start condition */
	push_sqk(&stack_op,&ele);
	while(isEmpty_sqk(&stack_op))
	{
		if('-'==*ep || '+'==*ep)
		{
			top_op = top_sqk(&stack_op);
			if('-'==top_op->name || '+'==top_op->name)	/* if low operator,if same FI low */
			{
				goto Deal;
			}
			else
			{
				ele.name = *ep;
				push_sqk(&stack_op,&ele);
				ep++;
				continue;
			}
		}
		if('*'==*ep || '/'==*ep)
		{
			top_op = top_sqk(&stack_op);
			if('*'==top_op->name || '/'==top_op->name)
			{
				goto Deal;
			}
			else
			{
				ele.name = *ep;
				push_sqk(&stack_op,&ele);
				ep++;
				continue;
			}
		}
		if('('==*ep)
		{
			ele.name = '(';
			push_sqk(&stack_op,&ele);
			ep++;
			continue;
		}		
		if(')'==*ep)
		{
			goto Deal;
		}
		if('\0'==*ep)
		{
			top_op = top_sqk(&stack_op);
			if('\0'==top_op->name)
			{
				pop_sqk(&stack_op,(S_element*)0);		/* exit the while condition */
				continue;
			}
			else
			{
				goto Deal;	
			}
		}
		ele.name = *ep;							/* by default, push number */
		push_sqk(&stack_nu,&ele);
		ep++;
		continue;
Deal:
		pop_sqk(&stack_op,&top);
		pop_sqk(&stack_nu,&r_nu);				/* be care the sequence */
		pop_sqk(&stack_nu,&l_nu);
		ele.name = (int)operate((int)l_nu.name,(int)r_nu.name,top.name);	
		push_sqk(&stack_nu,&ele);
		if('\0'==*ep)						/* when no input */
			continue;		
		if(')'==*ep)						/* the () is specific */
			pop_sqk(&stack_op,(S_element*)0);
		else
		{
			ele.name = *ep;					/* compute first, then push */
			push_sqk(&stack_op,&ele);
		}
		ep++;
		continue;
	}
	
	fprintf(stdout,"%d\n",(int)top_sqk(&stack_nu)->name);
	clear_sqk(&stack_nu);
	clear_sqk(&stack_op);
	destory_sqk(&stack_nu);
	destory_sqk(&stack_op);
	return 0;
}

/*
* operate the number
*/
signed int operate(int l_op,int r_op,char op)
{
	signed int rst = 0;
	do
	{
		if('+'==op)
		{
			rst = l_op + r_op;
			break;
		}
		if('-'==op)
		{
			rst = l_op - r_op;
			break;
		}
		if('*'==op)
		{
			rst = l_op * r_op;
			break;
		}
		if('/'==op)
		{
			rst = l_op / r_op;
			break;
		}
	}while(0);
	return rst;
}
